import java.util.ArrayList;
import java.util.Random;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Marc
 */
public class State {
   private ArrayList <Driver> drivers;
   private ArrayList <Person> travellers;
   private int n;
   private int m;
   public static int MAX_DISTANCE = 30000;
   public static String MOVE = "Swap Travellers";
   public static String DELETE = "Delete driver and add traveller";
   public static String DELETE2 = "Delete driver and add with his travellers";
   public static String SWAP = "Change order of trace";
   public static String ADD = "Add driver";
   public static String SWAPCAR = "SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwap travellers in the same car";

   public State(int n, int m){
       drivers = new ArrayList <Driver>();
       travellers = new ArrayList <Person> ();
       this.n = n;
       this.m = m;
       ini(n, m);
   }
   
   public State(State s) {
       drivers = new ArrayList<Driver>();
       for (int i = 0; i < s.drivers.size(); ++i) {
           drivers.add(new Driver (s.drivers.get(i)));
       }
       travellers = new ArrayList<Person>();
       for (int i = 0; i < s.travellers.size(); ++i) {
           travellers.add(new Person(s.travellers.get(i).getid(),
                   s.travellers.get(i).getini(), s.travellers.get(i).getfi()));
       }
       n = s.n;
       m = s.m;
       
   }

   /**
    * 
    * @param n
    * @param m
    */
   private void ini(int n, int m) {
       Random myRandom = new Random(System.nanoTime());
       for (int i = 0; i < n; ++i) {
           Point p1 = new Point (myRandom.nextInt(100), myRandom.nextInt(100));
           Point p2 = new Point (myRandom.nextInt(100), myRandom.nextInt(100));
           travellers.add(new Person(i+1, p1, p2));
       }
       IniStateRandom(n, m);
       //IniStateGreedy(n, m);

   }
   
   private void IniStateRandom(int n, int m) {
       Random R = new Random(System.nanoTime());
       int k =  R.nextInt(n-m)+1;
       //int k = 2;
       for (int i = 0; i < k; ++i){
           Driver daux = new Driver (travellers.get(0).getid(),
                                     travellers.get(0).getini(),
                                     travellers.get(0).getfi());
           travellers.remove(0);
           drivers.add(daux);
       }
       for (int i = 0; i < k; ++i){
           for (int j = i*n/k; j < (i+1)*n/k && j < travellers.size(); ++j) {
               drivers.get(i).addTraveller(travellers.get(j));
           }
       }
   }

   Integer abs(Integer x) {
       if (x > 0) return -x;
       return x;
   }

   Integer getDist(Point [] P) {
       Integer d = 0;
       for (int i = 1; i < P.length; ++i) {
           d += abs(P[i-1].getx() - P[i].getx()) +
                abs(P[i-1].gety() - P[i].gety());
       }
       return d;
       
   }
   private void bestTrace(Driver dr) {
       Driver bestDr = new Driver(dr);
       int bestDist = dr.getTraceDistance();
       int[] T = dr.getIdTravellers();
       //System.out.println("###############################################");
       //System.out.println(dr.getTrace());
       for (int i = 0; i < 2; ++i) {
           dr.swapTravellers(T[0], false);
           //System.out.println(dr.getTrace());
           if (dr.getTraceDistance() < bestDist) {
               bestDist = dr.getTraceDistance();
               bestDr = new Driver(dr);
           }
       }
       for (int i = 0; i < 2; ++i) {
           dr.swapTravellers(T[0], true);
           //System.out.println(dr.getTrace());
           if (dr.getTraceDistance() < bestDist) {
               bestDist = dr.getTraceDistance();
               bestDr = new Driver(dr);
           }
       }
       //System.out.println(bestDr.getTrace());
       //System.out.println("###############################################");
       dr = bestDr;
   }

   private void IniStateGreedy(int n, int m) {
       int d = (n-m);
       for (int i = 0; i < d; ++i){
           Driver daux = new Driver (travellers.get(0).getid(),
                                     travellers.get(0).getini(),
                                     travellers.get(0).getfi());
           travellers.remove(0);
           drivers.add(daux);
       }
       boolean [] picked = new boolean [travellers.size()];
       //for (int i = 0; i < drivers.size(); ++i) picked[i] = true;
       for (int i = 0; i < picked.length; ++i) picked[i] = false;
       //int assignedT = 0;
       for (int i = 0; i < drivers.size(); ++i) {
           int r = 0;
           int s = 1;
           int bestDistance = Integer.MAX_VALUE;
           Driver bestDr = new Driver (drivers.get(i));
           for (int j = 0; j < travellers.size(); ++j) {
               for (int k = j+1; k < travellers.size(); ++k) {
                   //System.out.println(" driver "+ i +" trav " + j + " trav " + k);
                   if (!picked[j] && !picked[k]) {
                       drivers.get(i).addTraveller(travellers.get(j));
                       drivers.get(i).addTraveller(travellers.get(k));
                       bestTrace(drivers.get(i));
                       if (drivers.get(i).getTraceDistance() < bestDistance) {
                           r = j;
                           s = k;
                           bestDistance = drivers.get(i).getTraceDistance();
                           bestDr = new Driver(drivers.get(i));
                       }
                       drivers.get(i).deleteTraveller(travellers.get(j).getid());
                       drivers.get(i).deleteTraveller(travellers.get(k).getid());
                   }
               }
           }
           drivers.set(i, bestDr);
           //System.out.println(drivers.get(i).getTrace());
           //assignedT += 2;
           picked[r] = true;
           picked[s] = true;
        }
       int TA = 0;
       for (int i = 0; i < picked.length; ++i) {
           if (picked[i]) {
               Random R = new Random(System.nanoTime());
               int drp = R.nextInt(drivers.size() -1);
               drivers.get(drp).addTraveller(travellers.get(i));
           }
       }
       if (TA > 0) {
           // reassignar els que queden
       }
       System.out.println("assigned travellers -> " + TA + " of "
                                                     + travellers.size() );
    }
 

   public void move (Driver dr1, Driver dr2, int id) {
       dr1.deleteTraveller(id);
       Person p = null;
       for (int i = 0; i < travellers.size() && p == null; ++i)
           if (travellers.get(i).getid() == id)
               p = travellers.get(i);
       dr2.addTraveller(p);
   }

    public boolean swapInCar(Driver d, int id1, int id2) {
       return d.swapInCar(id1, id2);
   }

   public boolean swapTravellers(Driver dr, int id, boolean ini){
        return dr.swapTravellers(id, ini);
   }

   public boolean deleteDriver (int posDriver1, int posDriver2){
       Driver dr1 = drivers.get(posDriver1);
       Driver dr2 = drivers.get(posDriver2);
       if(dr1.getNTravellers() == 0) {
            drivers.remove(dr1);
            Person p = dr1;
            dr2.addTraveller(p);
            return true;
       }
       return false;
   }

   public boolean deleteDriverWithTravellers (int posDriver1, int posDriver2){
       Driver dr1 = drivers.get(posDriver1);
       Driver dr2 = drivers.get(posDriver2);
       dr2.addTravellers(dr1.getTrace(), dr1.getp_23());
       drivers.remove(dr1);
       Person p = dr1;
       dr2.addTraveller(p);
       return true;
   }


   public int getNDrivers(){
       return drivers.size();
   }

   public int getN(){
       return n;
   }

   public int getM(){
       return m;
   }

   public int getDistanceDriver(int i){
       return drivers.get(i).getTraceDistance();
   }

   public int distance(){
       int sum = 0;
       int n = drivers.size();
       for (int i = 0; i < n; ++i){
            sum+=drivers.get(i).getTraceDistance();
       }
       return sum;
   }
   
   public boolean addDriver(int id) {
       boolean b = false;
       Person p = null;
       for (int i = 0; i < n-m - drivers.size(); ++i) {
           if (travellers.get(i).getid() == id) {
               b = true;
               p = travellers.get(i);
           }
       }
       if (!b) return false;
       Driver d = null;
       for (int i = 0; i < drivers.size() && d == null; ++i) {
           if (drivers.get(i).contains(p))
               d = drivers.get(i);
       }
       if (d != null)d.deleteTraveller(p.getid());
       drivers.add(new Driver(p.getid(), p.getini(), p.getfi()));
       return true;
   }

   public void printState (){
       for(int i = 0; i < travellers.size(); ++i){
           System.out.println("[" + travellers.get(i).getid() + travellers.get(i).getini().toString() +
            "| "+ travellers.get(i).getfi().toString());
       }
       System.out.println();
       for(int i = 0; i < drivers.size(); ++i){
           System.out.println("[" + drivers.get(i).getid() + drivers.get(i).getini().toString() +
            "| "+ drivers.get(i).getfi().toString());
       }
   }

    public Driver getDriver(int i) {
        return drivers.get(i);
    }

    public int[] getAvaliableDrivers() {
        //System.out.println("Drivers.size() = " + drivers.size());
        int res[] = new int[n-m - drivers.size()];
        for (int i = 0; i < n-m - drivers.size(); ++i) {
            res[i] = travellers.get(i).getid();
        }
        return res;
    }
      

}
